package leetcode

//https://leetcode.com/problems/permutations/
/**
 * 给定一组不包含重复数字的数组，求所有数字的全排列
 */
fun main(args: Array<String>) {

    println(permute(intArrayOf(1, 2, 3)))

    println(permuteDynamicProgramme(intArrayOf(1,2,3,4)))
}

fun permute(nums: IntArray): List<List<Int>> {

    val result = arrayListOf<List<Int>>()
    permuteRecursive(nums, arrayListOf(), result)
    return result
}

/**
 * 使用递归做
 */
fun permuteRecursive(nums: IntArray, tmp: ArrayList<Int>, result: ArrayList<List<Int>>) {

    if (tmp.size == nums.size) {
        result.add(ArrayList(tmp))
    } else {
        for (i in 0 until nums.size) {
            if (tmp.contains(nums[i])) continue
            tmp.add(nums[i])
            permuteRecursive(nums, tmp, result)  //1
            tmp.removeAt(tmp.lastIndex) //如果1是最后一次递归，那么递归完之后回到这里就移除掉最后一个，下次循环添加另一个
        }
    }
}

/**
 * 使用动态规划来做，比较好理解，但是比较耗内存，因为需要不断生成list保存之前的排列结果
 * n =1 a1
 * n =2  a1a2  a2a1
 *
 * n =3  在n=2的基础上，在每个位置都放置一个a3：
 * a3a1a2 、a1a3a2、 a1a2a3、 a3a2a1、 a2a3a1、a2a1a3
 *
 * 其实就符合动态规划的特点
 */
//DP
fun permuteDynamicProgramme(nums: IntArray): List<List<Int>> {

    val dp = Array(nums.size, { arrayListOf<List<Int>>() })
    if (nums.isEmpty()) return dp[0]
    dp[0].add(arrayListOf(nums[0]))

    var i = 1

    while (i < nums.size) {
        val lists = dp[i - 1]  //取出n = i-1 时的所有组合
        var j = 0
        while (j <lists.size) {   //遍历每个排列
            val list = lists[j]
            var k = 0
            while (k <= list.size) {  //在每个排列的每个位置插入i
                val newAddList = ArrayList(list)
                newAddList.add(k, nums[i])
                dp[i].add(newAddList)
                k++
            }
            j++
        }

        i++
    }

    return dp[nums.size - 1]
}